/**
 * 
 */
package string.passed2;

import java.util.Arrays;

/**
 * @author Michael
 * @since 01/06/2013
 */

/**
 * '?' Matches any single character.
 * '*' Matches any sequence of characters
 * (including the empty sequence).
 * 
 * The matching should cover the entire input string (not partial).
 * 
 * The function prototype should be: bool isMatch(const char *s, const char *p)
 * 
 * Some examples: 
 * isMatch("aa","a") → false
 * isMatch("aa","aa") → true
 * isMatch("aaa","aa") → false
 * isMatch("aa", "*") → true 
 * isMatch("aa", "a*") → true 
 * isMatch("ab", "?*") → true 
 * isMatch("aab", "c*a*b") → false
 * 
 * Solution http://blog.csdn.net/hopeztm/article/details/8039777
 * http://blog.csdn.net/tingmei/article/details/8049926
 */
public class WildcardMatching {

    public static boolean isMatch(String s, String p) {
        // return isMatchRecursionHelp(s, p, 0, 0);
        return isMatchInterationHelp(s, p);
    }

    /**
     * Greedy
     * 
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatchGreedy(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        int si = 0; // current index in s
        int pi = 0; // current index in p
        int pStar = -1; // the last * index from now
        int sStar = 0; // the last index in s match the * in p

        while (si < sLen) {
            while (pi < pLen && p.charAt(pi) == '*') {
                pStar = pi++;
                sStar = si;
            }

            if (pi == pLen
                    || (s.charAt(si) != p.charAt(pi) && p.charAt(pi) != '?')) {
                if (pStar == -1) {
                    return false;
                }
                si = ++sStar; // match 1 char in s
                pi = pStar + 1;
            } else {
                pi++;
                si++;
            }
        }

        while (pi < pLen && p.charAt(pi) == '*') {
            pi++;
        }

        return pi == pLen;
    }

    /**
     * http://discuss.leetcode.com/questions/222/wildcard-matching
     * DP
     * 
     *    s:  A  D  E  B
     *    p:  A*
     *       
     *       0  1  2  3  4
     *    0  f  f  f  f  t
     *    1  t  t  t  t  t 
     *    
     *    	 0  1  2  3  4
     *    0  f  f  f  f  f
     *    1  t  t  t  t  t
     * @param s
     * @param p
     * @return
     */
    public boolean isMatchDP(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();

        boolean[][] dp = new boolean[2][sLen + 1];
        dp[pLen % 2][sLen] = true;

        for (int pi = pLen - 1; pi >= 0; pi--) {
            Arrays.fill(dp[pi % 2], false);
            if (p.charAt(pi) == '*') {
                for (int si = sLen; si >= 0; si--) {
                    if (dp[(pi + 1) % 2][si]) {
                        for (; si >= 0; si--)
                            dp[pi % 2][si] = true;
                    }
                }
            } else {
                for (int si = sLen - 1; si >= 0; si--) {
                    dp[pi % 2][si] = (p.charAt(pi) == s.charAt(si) || p
                            .charAt(pi) == '?')
                            && dp[(pi + 1) % 2][si + 1];
                }
            }
        }
        return dp[0][0];
    }

    public static boolean isMatchInterationHelp(String str, String pattern) {
        if (str == null || pattern == null)
            return false;

        int si = 0;// str index meet the most last * in pattern
        int pi = 0;// pattern index just after most last *
        boolean star = false;// meet star?
        int i = 0;// index

        while (i + si < str.length()) {
            if (pi + i == pattern.length()) {
                if (!star)
                    return false;
                si++;
                i = 0;
                continue;
            }

            switch (pattern.charAt(pi + i)) {
            case '?':
                i++;
                break;
            case '*':
                star = true;
                pi += i;
                si += i;
                while (pi < pattern.length() && pattern.charAt(pi) == '*') {
                    pi++;
                }
                if (pi == pattern.length())
                    return true;
                i = 0;
                break;
            default:
                if (str.charAt(si + i) != pattern.charAt(pi + i)) {
                    if (!star)
                        return false;
                    si++;
                    i = 0;
                } else {
                    i++;
                }
                break;
            }
        }

        pi += i;
        while (pi < pattern.length() && pattern.charAt(pi) == '*') {
            pi++;
        }

        return pi == pattern.length();
    }

    public static boolean isMatchRecursionHelp(String str, String pattern,
            int si, int pi) {
        if (str == null || pattern == null)
            return false;

        if (pattern.length() == pi)
            return str.length() == si;

        if (str.length() == si) {
            return pattern.charAt(pi) == '*' ? isMatchRecursionHelp(str,
                    pattern, si, pi + 1) : false;
        }

        if (pattern.charAt(pi) != '*') {
            if (pattern.charAt(pi) == '?'
                    || pattern.charAt(pi) == str.charAt(si)) {
                return isMatchRecursionHelp(str, pattern, si + 1, pi + 1);
            } else {
                return false;
            }
        }

        return isMatchRecursionHelp(str, pattern, si + 1, pi)
                || isMatchRecursionHelp(str, pattern, si, pi + 1);
    }

    /*
     * '?' Matches any single character. '*' Matches zero or more characters.
     * str: string to check pattern: pattern to match si: string index pi:
     * pattern index
     */
    public static boolean match(char[] str, char[] pattern, int si, int pi) {
        if (str == null || pattern == null)
            return false;

        // pattern characters have all been matched
        if (pattern.length == pi)
            return str.length == si;

        if (str.length == si)
            return pattern[pi] == '*' ? match(str, pattern, si, pi + 1) : false;

        // if current pattern character is not '*', must match current
        // characters
        if (pattern[pi] != '*') {
            // current characters match, go further for both
            if (str[si] == pattern[pi] || pattern[pi] == '?') {
                return match(str, pattern, si + 1, pi + 1);
            }
            // current characters don't match
            else {
                return false;
            }
        }

        // current pattern character is '*'
        return match(str, pattern, si + 1, pi)
                || match(str, pattern, si, pi + 1);
    }

    // good for interview
    public static boolean matchR0(char[] str, char[] pattern, int si, int pi) {
        assert (str != null && pattern != null && si <= str.length && pi <= pattern.length);

        // If pattern reaches end, str must reach end as well
        if (pi == pattern.length)
            return si == str.length;

        // If str reaches end first, check if pattern still has '*' left.
        if (si == str.length) {
            return pattern[pi] == '*' ? matchR0(str, pattern, si, pi + 1)
                    : false;
        }

        if (pattern[pi] != '*') {
            if (pattern[pi] == str[si] || pattern[pi] == '?') {
                return matchR0(str, pattern, si + 1, pi + 1);
            } else
                return false;
        }

        return matchR0(str, pattern, si + 1, pi)
                || matchR0(str, pattern, si, pi + 1);
    }

    /**
     * 
     */
    public WildcardMatching() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        String[] ss = { "", "aaaa", "a", "aa", "aa", "aa", "ab", "abcde",
                "aab", "ab" };
        String[] ps = { "*", "*a", "b", "a", "b*a", "*", "ab*", "ab?*e",
                "?a*b", "?*b" };
        for (int i = 0; i < ss.length; i++)
            System.out.println(ss[i] + ", " + ps[i] + ": "
                    + isMatchGreedy(ss[i], ps[i]));
    }

}
